#include "iostream"
#include "stdlib.h"
using namespace std;
// sequence list

#define MaxSize 10
#define InitSize 10

struct ElemType{
	int n;
	ElemType *next;
};

typedef struct LNode{
	ElemType data;
	LNode* next;
}LNode,*LinkList;

bool initList(LinkList &L);
void increaseSize(LinkList &L,int length);

bool insert(LinkList &L,int i,ElemType e);
bool insertPrior(LinkList &L,ElemType e);
bool del(LinkList &L,int i,ElemType &e);
bool del(LNode *p);

LNode * getElem(LinkList L,int i);
LNode * locateElem(LinkList L,ElemType e);

void destoryList(LinkList &L);
void printList(LinkList L);

int length(LinkList L);
bool isEmpty(LinkList L);

int main(){
	
	LinkList L;
	initList(L);
	ElemType e;
	e.n=1;
	insert(L,1,e);
	e.n=2;
	insert(L,1,e);
	e.n=3;
	insert(L,1,e);
	e.n=4;
	insert(L,1,e);
	printList(L);
	return 0;
}

// init List no have head node
//bool initList(LinkList &L){
//	L = NULL;
//	return true;
//}

// init List have head node
bool initList(LinkList &L){
	L=(LNode *) malloc (sizeof(LNode));
	if(L==NULL)
		return false;
	L->next = NULL;
	return true;
}

bool insert(LinkList &L,int i,ElemType e){
	if(i<1){
		return false;
	}
	LNode *p;
	int j=0;
	p=L;
	while(p!=NULL && j<i-1){
		p=p->next;
		j++; 
	}
	if(p==NULL)
		return false;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//tail insert
bool addTail(LinkList &L,ElemType e){
	
	LNode *p=L;
	while(p->next!=NULL)
		p=p->next;
		
	LNode* s = (LNode *)malloc(sizeof(LNode));
	s->next = NULL;
	s->data = e;
	s = p;
	p->next = s;
	
	return true;
	
}

bool addHead(LinkList &L,ElemType e){
	LNode* s = (LNode *)malloc(sizeof(LNode));
	s->next = L->next;
	s->data = e;
	L->next = s;
	return true;
}

void printList(LinkList L){
	LNode* p = L->next;
	while(p!=NULL){
		printf("%d",p->data.n);
		p=p->next;
	}
}

// O(n)
//bool insertPrior(LinkList &L,LNode* p,ElemType e){
//	if(L==NULL)
//		return false;
//	LNode* t = L;
//	while(t->next!=p){
//		t=t->next;
//		if(t==NULL)
//			return false;
//	}
//	LNode* s = (LNode*)malloc(sizeof(LNode));
//	if(s==NULL)
//		return false;
//	s->next = p;
//	t->next = s;
//}


//O(1)
bool insertPrior(LNode* p,ElemType e){
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if(s==NULL)
		return false;
	s->data = p->data;
	p->data = e;
	
	s->next = p->next;
	p->next = s;
	return true;
}

//O(n)
bool del(LinkList &L,int i,ElemType &e){
	if(i<1)
		return false;
	int j=0;
	LNode* p = L;
	while(p->next == NULL && j<i-1){
		p=p->next;
		j++;
	}
	if(p==NULL || p->next == NULL )
		return false;
	
	LNode *q = p->next;
	p->next = q->next;
	e = q->data;
	free(q);
	return true;
	
}
//O(1) it doesn't work that delete the tail node;
bool del(LNode *p){
	if(p==NULL)
		return false;
	LNode * q = p->next;
	p->data = q->data;
	p->next = p->next->next;
	free(q);
	return true;
}

LNode * getElem(LinkList L,int i){
	if(i<0)
		return NULL;
		
	LNode* p = L;
	int j=0;
	while(p!=NULL && j<i){
		printf("%d",p->data.n);
		p=p->next;
		j++;
	}
	return p;
}

LNode * locateElem(LinkList L,ElemType e){
	LNode *p=L->next;
	while(p!=NULL && p->data.n !=e.n)
		p = p->next;
	return p;
}


int length(LinkList L){
	int len = 0;
	LNode * p = L;
	while(p->next != NULL){
		p=p->next;
		len++;
	}
	return len;
}








